package LCR;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class maxProduct {
    //如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)，则可以将总时间复杂度降低到 O(n)。
    // 可以使用位运算预处理每个单词，通过位运算操作判断两个单词是否有公共字母。由于单词只包含小写字母，
    // 共有 26 个小写字母，因此可以使用位掩码的最低 26 位分别表示每个字母是否在这个单词中出现。将 a 到 z
    // 分别记为第 0 个字母到第 25 个字母，则位掩码的从低到高的第 i 位是 1 当且仅当第 i 个字母在这个单词
    // 中，其中 0≤i≤25。
    //用数组 masks 记录每个单词的位掩码表示。计算数组 masks 之后，判断第 i 个单词和第 j 个单词是否有公
    // 共字母可以通过判断 masks[i]&masks[j] 是否等于 0 实现，当且仅当 masks[i]&masks[j]=0 时第 i 个
    // 单词和第 j 个单词没有公共字母，此时使用这两个单词的长度乘积更新单词长度的最大乘积。


    // | ： 有一个为1 就为1；全为0才为0

    public int maxProduct(String[] words) {
        int length = words.length;
        int[] masks = new int[length];
        for (int i = 0; i < length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                masks[i] = masks[i] | (1 << (word.charAt(j) - 'a'));
            }
        }

        int ret = 0;

        for(int i = 0;i < length;i++) {
            for(int j = i +1 ;j < length;j++) {
                if((masks[i] & masks[j]) == 0) {
                    int tem = words[i].length() * words[j].length();
                    if(ret < tem) {
                        ret = tem;
                    }
                }
            }
        }
        return ret;

    }

    //Map
    public int maxProduct2(String[] words) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = words.length;
        for (int i = 0; i < length; i++) {
            int mask = 0;
            String word = words[i];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                mask |= 1 << (word.charAt(j) - 'a');
            }
            if (wordLength > map.getOrDefault(mask, 0)) {
                map.put(mask, wordLength);
            }
        }
        int maxProd = 0;
        Set<Integer> maskSet = map.keySet();
        for (int mask1 : maskSet) {
            int wordLength1 = map.get(mask1);
            for (int mask2 : maskSet) {
                if ((mask1 & mask2) == 0) {
                    int wordLength2 = map.get(mask2);
                    maxProd = Math.max(maxProd, wordLength1 * wordLength2);
                }
            }
        }
        return maxProd;
    }
}
